# -*- coding: utf-8 -*-
"""
@author:  yinbing.li(yinbing.li@zillnk.com)
@version: 1.0.0
@file:    leetcode733_像素渲染(DFS-BFS).py
@time:    2023/3/7 18:03
"""
import collections
from typing import List


class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        if image[sr][sc] == color:
            return image

        # n为二维数组行数，m为二维数组列数，src为原始值
        n, m = len(image), len(image[0])
        src = image[sr][sc]

        # 维护一个和image相同大小的二维数组，避免向队列中重复添加数据，原始数据均为0，当image中某个元素被使用后，flag数组相应位置元素置为1
        flag = []
        for i in range(n):
            flag.append([0 for i in range(len(image[0]))])

        queue = collections.deque()
        queue.appendleft((sr, sc))

        while len(queue) != 0:
            x, y = queue.pop()
            image[x][y] = color
            flag[x][y] = 1

            # 遍历上下左右节点
            dirs = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
            for i in dirs:
                if 0 <= i[0] < n and 0 <= i[1] < m and image[i[0]][i[1]] == src and flag[i[0]][i[1]] == 0:
                    flag[i[0]][i[1]] = 1
                    queue.appendleft(i)
        return image
